package algorithm.doublePointer;

import java.util.Arrays;

// 有效三角形的个数
public class LC311 {
    public int triangleNumber(int[] nums) {
        int ans = 0, len = nums.length;
        if (len < 3) {
            return 0;
        }

        // 给数组排序
        Arrays.sort(nums);

        // 固定一个最大长度的值
        for (int i = len - 1; i >= 2; i--) {
            // 利用双指针
            int l = 0, r = i - 1;
            while (l < r) {
                if (nums[l] + nums[r] > nums[i]) {
                    ans += r - l;
                    r--;
                } else {
                    l++;
                }
            }
        }
        return ans;
    }
}
